#!/usr/bin/env python
# -*- indent-tabs-mode: nil; tab-width: 4; coding: utf-8 -*-
# vi: set ts=4 sts=4 sw=4 set smarttab set expandtab
#http://www.careercup.com/question?id=14633700
#Facebook interview question
"""
Determine winner of 2/9 number game

Two players play the following game: they pick a random number N (less than 2 billion) then, 
starting from 1, take turns multiplying the number from the previous turn with either 2 or 9 (their choice). 
Whoever reaches N first wins. 
The candidate should write a function that given N decides who wins (first or second player)?
"""

def get_winner(n, buf):
    if n <= 9: return 1
    if n in buf: return buf[n]
    result = 2
    if get_winner((n + 8) / 9, buf) == 2: result = 1
    elif get_winner((n + 1) / 2, buf) == 2: result = 1
    buf[n] = result
    return result
    

buf = {}
[get_winner(i, buf) for i in range(100, 1000)]

print buf 
